package leetcode.code1031;

public class Solution {

	public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
		int len = nums.length;
		long[] sums = new long[len + 1];
		for (int i = 1; i < sums.length; i++) {
			sums[i] = sums[i - 1] + nums[i - 1];
		}
		long[] f = new long[len];
		long[] s = new long[len];
		long F = 0, S = 0;
		for (int i = 1; i <= len; i++) {
			if (i >= firstLen) {
				long sum = sums[i] - sums[i - firstLen];
				F = Math.max(F, sum);
				f[i - 1] = F;
			}
			if (i >= secondLen) {
				long sum = sums[i] - sums[i - secondLen];
				S = Math.max(S, sum);
				s[i - 1] = S;
			}
		}
		long ans = 0;
		F = 0;
		S = 0;
		for (int i = len; i >= 1; i--) {
			if (i + firstLen <= len) {
				long sum = sums[i + firstLen] - sums[i];
				F = Math.max(F, sum);
			}
			if (i + secondLen <= len) {
				long sum = sums[i + secondLen] - sums[i];
				S = Math.max(S, sum);
			}
			ans = Math.max(ans, F + s[i - 1]);
			ans = Math.max(ans, S + f[i - 1]);
		}
		return (int) ans;
	}

}
